import java.util.*;

/**
 * 399. 除法求值
 * https://leetcode-cn.com/problems/evaluate-division/
 */
public class Solutions_399 {
    public static void main(String[] args) {
//        List<List<String>> equations = {{"a", "b"}, {"b", "c"}};
//        double[] values = {2.0, 3.0};
//        List<List<String>>queries = {{"a", "c"}, {"b", "a"}, {"a", "e"}, {"a", "a"}, {"x", "x"}};  // output: {6.00000, 0.50000, -1.00000, 1.00000, -1.00000}

        List<List<String>> equations = new ArrayList<>();
        equations.add(Arrays.asList("a", "b"));
        equations.add(Arrays.asList("b", "c"));
        equations.add(Arrays.asList("bc", "cd"));

        double[] values = {1.5, 2.5, 5.0};

        List<List<String>> queries = new ArrayList<>();
        queries.add(Arrays.asList("a", "c"));
        queries.add(Arrays.asList("c", "b"));
        queries.add(Arrays.asList("bc", "cd"));
        queries.add(Arrays.asList("cd", "bc"));
        // output: {3.75000, 0.40000, 5.00000, 0.20000}

//        List<List<String>> equations = {{"a", "b"}};
//        double[] values = {0.5};
//        List<List<String>> queries = {{"a", "b"}, {"b", "a"}, {"a", "c"}, {"x", "y"}};  // output: {0.50000, 2.00000, -1.00000, -1.00000}

        double[] result = calcEquation(equations, values, queries);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 解法一：广度优先搜索
     */
    public static double[] calcEquation(List<List<String>> equations,
                                        double[] values, List<List<String>> queries) {
        double[] res = new double[queries.size()];
        Map<String, Integer> map = new HashMap<>();
        int cnt = 0;
        // 为顶点标记唯一标识
        for (List<String> list : equations) {
            String node1 = list.get(0);
            String node2 = list.get(1);
            if (!map.containsKey(node1)) {
                map.put(node1, cnt++);
            }
            if (!map.containsKey(node2)) {
                map.put(node2, cnt++);
            }
        }
        // 数组中存放 list 列表
        // list[0] = ArrayList，顶点 0，连接的其他顶点
        List<Pair_399>[] edges = new List[cnt];
        for (int i = 0; i < cnt; i++) {
            // 初始化对象
            edges[i] = new ArrayList<>();
        }
        // 构造
        for (int i = 0; i < equations.size(); i++) {
            List<String> eq = equations.get(i);
            String node1 = eq.get(0);
            String node2 = eq.get(1);
            int idx1 = map.get(node1);
            int idx2 = map.get(node2);
            // node1 节点到达 node2 节点需要的值
            edges[idx1].add(new Pair_399(idx2, values[i]));
            // node2 节点到达 node1 节点需要的值
            edges[idx2].add(new Pair_399(idx1, 1 / values[i]));
        }
        // 计算
        for (int i = 0; i < queries.size(); i++) {
            double ans = -1.0;
            List<String> query = queries.get(i);
            // 判断两个顶点是否都存在
            String node1 = query.get(0);
            String node2 = query.get(1);
            int idx1 = map.getOrDefault(node1, -1);
            int idx2 = map.getOrDefault(node2, -1);
            if (idx1 == -1 || idx2 == -1) {
                res[i] = ans;
                continue;
            }
            if (idx1 == idx2) {
                res[i] = 1;
                continue;
            }
            Queue<Integer> queue = new LinkedList<>();
            queue.add(idx1);
            double[] ratios = new double[cnt];
            // 防止重复访问，造成死循环
            Arrays.fill(ratios, -1);
            ratios[idx1] = 1.0;

            while (!queue.isEmpty() && ratios[idx2] < 0) {
                int x = queue.poll();
                for (Pair_399 pair : edges[x]) {
                    // x 顶点与哪些顶点直接连通
                    int y = pair.index;
                    if (ratios[y] < 0) {
                        ratios[y] = pair.val * ratios[x];
                        queue.add(y);
                    }
                }
            }
            res[i] = ratios[idx2];
        }
        return res;
    }
}

class Pair_399 {
    int index;  // 顶点索引
    double val;  // 到 index 顶点的路径值

    public Pair_399(int index, double val) {
        this.index = index;
        this.val = val;
    }
}
